﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TailRecursive
{
	class Program
	{
		/// <summary>
		/// 对递归有些了解的朋友一定猜得到，如果单项链表十分长，那么上面这个方法就可能会遇到栈溢出，
		/// 也就是抛出StackOverflowException。这是由于每个线程在执行代码时，都会分配一定尺寸的栈空间（Windows系统中为1M），
		/// 每次方法调用时都会在栈里储存一定信息（如参数、局部变量、返回地址等等），这些信息再少也会占用一定空间，
		/// 成千上万个此类空间累积起来，自然就超过线程的栈空间了。
		/// </summary>
		/// <param name="args"></param>
		static void Main(string[] args)
		{
			#region 斐波那契问题

			int fibonacciNotTail = FibonacciRecursively(10);
			int fibonacciTail = FibonacciTailRecursively(10);

			Console.WriteLine("斐波那契非尾递归的值：{0}", fibonacciNotTail);
			Console.WriteLine("斐波那契尾递归的值：{0}", fibonacciTail);

			#endregion

			#region 阶乘问题

			int factorialNotTail = FactorialRecursively(5);
			int factorialTail = FactorialTailRecursively(5);

			Console.WriteLine("阶乘非尾递归的值：{0}", factorialNotTail);
			Console.WriteLine("阶乘尾递归的值：{0}", factorialTail);

			int newFactorial = FactorialNewRecursively(5);
			Console.WriteLine("阶乘改造的值：{0}", newFactorial);

			Console.ReadLine();
			#endregion
		}

		#region 阶乘问题

		/// <summary>
		/// 非尾递归
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		public static int FactorialRecursively(int n)
		{
			if (n == 0) return 1;
			return FactorialRecursively(n - 1) * n;
		}

		/// <summary>
		/// 尾递归
		/// </summary>
		/// <param name="n"></param>
		/// <param name="r"></param>
		/// <returns></returns>
		public static int FactorialTailRecursively(int n, int r = 1)
		{
			if (n == 0) return r;
			return FactorialTailRecursively(n - 1, n * r);
		}

		#endregion

		#region 阶乘再次改造

		/*
		 * 每次计算n的阶乘时，其实是“先获取n - 1的阶乘”之后再“与n相乘并返回”
		 * FactorialContinuation方法的含义是“计算n的阶乘，并将结果传入continuation方法，并返回其调用结果”。
		 */


		/// <summary>
		/// 新的阶乘递归写法
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		public static int FactorialNewRecursively(int n)
		{
			return FactorialContinuation(n - 1, r => n * r);
		}

		//FactorialContinuation方法的实现可以这样表述：“计算n的阶乘，并将结果传入continuation方法并返回”，
		//也就是“计算n - 1的阶乘，并将结果与n相乘，再调用continuation方法”。
		//为了实现“并将结果与n相乘，再调用continuation方法”这个逻辑，代码又构造了一个匿名方法，再次传入FactorialContinuation方法。
		// 6. FactorialContinuation(n, x => x)
		public static int FactorialContinuation(int n, Func<int, int> continuation)
		{
			if (n == 0) return continuation(1);	  //递归的出口条件
			return FactorialContinuation(n - 1, r => continuation(n * r));
		}

		/*
		 * Continuation，即为“完成某件事情”之后“还需要做的事情”。
		 * 例如，在.NET中标准的APM调用方式，便是由BeginXXX方法和EndXXX方法构成，这其实便是一种Continuation：在完成了BeginXXX方法之后，还需要调用EndXXX方法。
		 */

		#endregion

		#region 斐波那契问题

		/// <summary>
		/// 非尾递归
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		public static int FibonacciRecursively(int n)
		{
			if (n < 2) return n;
			return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
		}

		/// <summary>
		/// 尾递归 我们则需要提供两个累加器
		/// </summary>
		/// <param name="n"></param>
		/// <param name="acc1">累加器1</param>
		/// <param name="acc2">累加器2</param>
		/// <returns></returns>
		public static int FibonacciTailRecursively(int n, int acc1=0, int acc2=1)
		{
			if (n == 0) return acc1;
			return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
		}

		#endregion

		#region  斐波那契再次改造

		/// <summary>
		/// 
		/// </summary>
		/// <param name="n"></param>
		/// <param name="continuation"></param>
		/// <returns></returns>
		public static int FibonacciContinuation(int n, Func<int, int> continuation)
		{
			if (n < 2) return continuation(n);	  //递归的出口条件
			return FibonacciContinuation(n - 1,
				r1 => FibonacciContinuation(n - 2,
					r2 => continuation(r1 + r2)));
		}

		#endregion

		#region 节点长度问题

		/// <summary>
		/// 非尾递归
		/// </summary>
		/// <param name="head"></param>
		/// <returns></returns>
		public static int GetLengthRecursively(Node head)
		{
			if (head == null) return 0;
			return GetLengthRecursively(head.Next) + 1;
		}

		/// <summary>
		/// 尾递归
		/// </summary>
		/// <param name="head"></param>
		/// <param name="acc"></param>
		/// <returns></returns>
		public static int GetLengthTailRecursively(Node head, int acc = 0)
		{
			if (head == null) return acc;
			return GetLengthTailRecursively(head.Next, acc + 1);
		}

		/*
		 * GetLengthTailRecursively方法多了一个acc参数，acc的为accumulator（累加器）的缩写，
		 * 它的功能是在递归调用时“积累”之前调用的结果，
		 * 并将其传入下一次递归调用中——这就是GetLengthTailRecursively方法与GetLengthRecursively方法相比在递归方式上最大的区别：
		 * GetLengthRecursive方法在递归调用后还需要进行一次“+1”，而GetLengthTailRecursively的递归调用属于方法的最后一个操作。
		 * 这就是所谓的“尾递归”。
		 */

		#endregion

		#region 二叉树

		/// <summary>
		/// 传统遍历方法
		/// </summary>
		/// <param name="root"></param>
		public static void PreOrderTraversal(TreeNode root)
		{
			if (root == null) return;

			Console.WriteLine(root.Value);
			PreOrderTraversal(root.Left);
			PreOrderTraversal(root.Right);
		}

		/// <summary>
		/// 尾递归用法
		/// </summary>
		/// <param name="root"></param>
		/// <param name="continuation"></param>
		public static void PreOrderTraversal(TreeNode root, Action<TreeNode> continuation)
		{
			if (root == null)
			{
				continuation(null);
				return;
			}

			Console.WriteLine(root.Value);

			PreOrderTraversal(root.Left,
				left => PreOrderTraversal(root.Right,
					right => continuation(right)));
		}

		/*
		 * 我们现在把每次递归调用都作为代码的最后一次操作
		 * 把接下来的操作使用Continuation包装起来，这样就实现了尾递归，避免了堆栈数据的堆积。
		 */

		#endregion

		/* 
		 * 在命令式编程中，我们解决一些问题往往可以使用循环来代替递归，这样便不会因为数据规模造成堆栈溢出。
		 * 但是在函数式编程中，要实现“循环”的唯一方法便是“递归”，因此尾递归和CPS对于函数式编程的意义非常重大。
		 * 了解尾递归，对于编程思维也有很大帮助，因此大家不妨多加思考和练习，让这样的方式为自己所用。
		 */
	}
}
